package ifrn.edu.br.tads.grafo;

import java.lang.management.GarbageCollectorMXBean;
import java.util.ArrayList;
import java.util.List;

public class Grafo {

	public static boolean possuiCaminhoEuleriano(List<Vertice> vertices) {
		
		int qtVerticesComGrauImpar = 0;
		
		//percorre todos os vertices
		for (Vertice vertice : vertices) {
			
			//o grau do vértice é determinado pela quantidade de arestas dele
			int grau = vertice.getArestas().size();
			
			//se possui grau impar armazena na variavel q informa a quantidade de grau impar
			if (grau%2 == 1) {
				qtVerticesComGrauImpar++;
			}
			
			//se tiver mais de 2 vértices com grau ímpar, o grafo não possui caminho euleriano
			if (qtVerticesComGrauImpar > 2) {
				return false;
			}
			
		}
		
		return true;
		
	}
	
	
	public static void main(String[] args) {
		
		List<Vertice> vertices = new ArrayList<>();
		
		Vertice v1 = new Vertice("v1");
		Vertice v2 = new Vertice("v2");
		Vertice v3 = new Vertice("v3");
		Vertice v4 = new Vertice("v4");
		Vertice v5 = new Vertice("v5");
		
		v1.addAresta(v2, 1);
		v1.addAresta(v3, 1);
		v1.addAresta(v4, 1);
		
		v2.addAresta(v1, 1);
		v2.addAresta(v5, 1);
		
		v3.addAresta(v1, 1);
		v3.addAresta(v4, 1);
		
		v4.addAresta(v1, 1);
		v4.addAresta(v3, 1);
		v4.addAresta(v5, 1);
		
		v4.addAresta(v2, 1);
		v4.addAresta(v4, 1);
		
		vertices.add(v1);
		vertices.add(v2);
		vertices.add(v3);
		vertices.add(v4);
		vertices.add(v5);
		
		System.out.println("Possui caminho euleriano? "+ Grafo.possuiCaminhoEuleriano(vertices));
	}
	
}
